package problem.year2021.march;

/**
 * 给你单链表的头节点 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 *  
 * 示例 1：
 * 输入：head = [1,2,3,4,5], left = 2, right = 4
 * 输出：[1,4,3,2,5]
 * 示例 2：
 * 输入：head = [5], left = 1, right = 1
 * 输出：[5]
 *  
 * 提示：
 * 链表中节点数目为 n
 * 1 <= n <= 500
 * -500 <= Node.val <= 500
 * 1 <= left <= right <= n
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class March18 {
    //      Definition for singly-linked list.
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 单向链表的反转需要借助next指针
        // 简单办法将所有的节点先存储起来，然后再翻转;根据其特性，只要换他们的值就OK了
        int len = right - left + 1;
        int[] ints = new int[len];
        // find this left node
        ListNode leftNode = head;
        for (int i = 1; i <= left; ++i) {
            if (leftNode.next != null){
                leftNode = leftNode.next;
            } else return head; // the linked list's length letter than the number of left
        }
        ListNode rightNode = leftNode; // recode the left node use trainer at follow
        // has find this left node, start check every one able node
        int i = 0;
        while (i < len){
            ints[i] = rightNode.val;
            if (rightNode.next != null) {
                rightNode = rightNode.next;
            } else break; // this right number more than the length of the linked list
            ++i;
        }
        // to reverse list node for index from left to right
        for (int j = 0; j < i; ++j) {
            leftNode.val = ints[i-j];
            leftNode = leftNode.next;
        }
        return head;
    }
}
